package cn.demoncat.util.lang.entity.data;

import java.util.function.Consumer;

import org.apache.commons.lang3.StringUtils;

import cn.demoncat.util.lang.constant.StringConstant;

/**
 * 图：邻接矩阵，无向图
 * 
 * @author 延晓磊
 *
 * @since 2020年7月24日
 */
public class ArrayGraph<T> {

	/**
	 * 顶点集
	 */
	private final T[] vertexes;
	/**
	 * 边集（邻接矩阵）
	 */
	private final int[][] edges;
	/**
	 * 顶点数
	 */
	private final int vertexSize;
	/**
	 * 边数
	 */
	private int edgeCount;
	
	/**
	 * 构建
	 * 
	 * @param vertexes	顶点集
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月24日
	 */
	public ArrayGraph(T[] vertexes) {
		super();
		this.vertexes = vertexes;
		this.vertexSize = vertexes.length;
		this.edges = new int[vertexSize][vertexSize];
		this.edgeCount = 0;
	}

	/**
	 * 顶点集
	 * 
	 * @return
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月24日
	 */
	public T[] getVertexes() {
		return vertexes;
	}
	
	/**
	 * 顶点
	 * 
	 * @param i	索引
	 * 
	 * @return
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月24日
	 */
	public T getVertexe(int i) {
		return vertexes[i];
	}
	
	/**
	 * 修改顶点
	 * 
	 * @param i
	 * @param vertex
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月24日
	 */
	public void setVertex(int i, T vertex) {
		vertexes[i] = vertex;
	}

	/**
	 * 顶点数
	 * 
	 * @return
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月24日
	 */
	public int getVertexSize() {
		return vertexSize;
	}
	
	/**
	 * 边集（邻接矩阵）
	 * 
	 * @return
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月24日
	 */
	public int[][] getEdges() {
		return edges;
	}

	/**
	 * 设置边
	 * 
	 * @param v1		顶点1的索引
	 * @param v2		顶点2的索引 
	 * @param weight	边的权值（0表示删除，非0表示添加/修改）
	 * 
	 * @return 旧的权值
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月24日
	 */
	public int setEdge(int v1, int v2, int weight) {
		// 当前权值
		int curr = edges[v1][v2];
		// 修改权值（无向图，对称矩阵-双向关联）
		edges[v1][v2] = weight;
		edges[v2][v1] = weight;
		// 操作类型
		if (curr == 0) {
			if (weight != 0) {
				// 0 > 非0 = 添加
				edgeCount ++;
			}
		}else if (weight == 0) {
			// 非0 > 0 = 删除
			edgeCount --;
		}
		return curr;
	}
	
	/**
	 * 删除边
	 * 
	 * @param v1		顶点1的索引
	 * @param v2		顶点2的索引 
	 * 
	 * @return 旧的权值
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月24日
	 */
	public int delEdge(int v1, int v2) {
		return setEdge(v1, v2, 0);
	}
	
	/**
	 * 边数
	 * 
	 * @return
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月24日
	 */
	public int getEdgeCount() {
		return edgeCount;
	}

	/**
	 * 边的权值
	 * 
	 * @param v1		顶点1的索引
	 * @param v2		顶点2的索引 
	 * 
	 * @return 边的权值
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月24日
	 */
	public int getWeight(int v1, int v2) {
		return edges[v1][v2];
	}
	
	/**
	 * 显示图形（对称矩阵）
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月24日
	 */
	public void show() {
		// 顶点
		System.out.println(StringUtils.join(vertexes, "\t"));
		// 矩阵
		System.out.println("————————————————————————————————————————————————");
		for (int[] is : edges) {
			for (int i : is) {
				System.out.print(i + "\t");
			}
			System.out.println(StringConstant.NEW_LINE);
		}
	}
	
	/**
	 * 获取第一个邻接顶点
	 * 
	 * @param index	顶点索引
	 * 
	 * @return	邻接顶点索引
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月24日
	 */
	public int getFirstNeighbor(int index) {
		for (int i = 0; i < vertexSize; i++) {
			if (edges[index][i] != 0) {
				return i;
			}
		}
		return -1;
	}
	
	/**
	 * 获取下一个邻接顶点
	 * 
	 * @param index	顶点索引
	 * @param curr	当前邻接顶点索引
	 * 
	 * @return	邻接顶点索引
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月24日
	 */
	public int getNextNeighbor(int index, int curr) {
		for (int i = curr + 1; i < vertexSize; i++) {
			if (edges[index][i] != 0) {
				return i;
			}
		}
		return -1;
	}
	
	/**
	 * 遍历 - 深度优先搜索（Depth First Search）
	 * 
	 * @param fn	消费（顶点）
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月24日
	 */
	public void dfs(Consumer<T> fn) {
		// 访问标识
		boolean[] visits = new boolean[vertexSize];
		// 遍历顶点，逐个挖掘
		for (int i = 0; i < vertexSize; i++) {
			if (!visits[i]) {
				dfs(visits, i, fn);
			}
		}
	}
	
	/**
	 * 遍历 - 深度优先搜索（Depth First Search）
	 * 
	 * @param visits	访问标识
	 * @param index		当前顶点索引
	 * @param fn		消费（顶点）
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月24日
	 */
	private void dfs(boolean[] visits, int index, Consumer<T> fn) {
		// 消费当前顶点
		fn.accept(vertexes[index]);
		// 设置为已访问
		visits[index] = true;
		// 查找第一个邻接顶点
		int w = getFirstNeighbor(index);
		while (w != -1) {
			// 未访问
			if (!visits[w]) {
				// 邻接顶点作为初始顶点，纵向递归挖掘
				dfs(visits, w, fn);
			}
			// 查找下一个邻接顶点
			w = getNextNeighbor(index, w);
		}
	}
	
	/**
	 * 遍历 - 广度优先搜索（Broad First Search）
	 * 
	 * @param fn	消费（顶点）
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月24日
	 */
	public void bfs(Consumer<T> fn) {
		// 访问标识
		boolean[] visits = new boolean[vertexSize];
		// 遍历顶点，逐个挖掘
		for (int i = 0; i < vertexSize; i++) {
			if (!visits[i]) {
				bfs(visits, i, fn);
			}
		}
	}
	
	/**
	 * 遍历 - 广度优先搜索（Broad  First Search）
	 * 
	 * @param visits	访问标识
	 * @param index		当前顶点索引
	 * @param fn		消费（顶点）
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月24日
	 */
	private void bfs(boolean[] visits, int index, Consumer<T> fn) {
		// 队列头
		int u;
		// 邻接顶点
		int w;
		// 队列
		Queue<Integer> queue = new ArrayQueue<>(vertexSize);
		
		// 消费当前顶点
		fn.accept(vertexes[index]);
		// 设置为已访问
		visits[index] = true;
		// 加入队列
		queue.add(index);
		
		while (!queue.isEmpty()) {
			// 取出队列头
			u = queue.get();
			// 查找第一个邻接顶点
			w = getFirstNeighbor(u);
			while (w != -1) {
				// 未访问
				if (!visits[w]) {
					// 消费当前顶点
					fn.accept(vertexes[w]);
					// 设置为已访问
					visits[w] = true;
					// 加入队列
					queue.add(w);
				}
				// 逐层，横向循环挖掘
				w = getNextNeighbor(u, w);
			}
		}
	}
}
